# 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
#  注意 这个数列必须是 严格 递增的。
#
#  示例 1:
# 输入: [1,3,5,4,7]
# 输出: 2
# 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
#
#  示例 2:
# 输入: [2,2,2,2,2]
# 输出: 5
# 解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
from typing import List


class Solution:
    def findNumberOfLIS2(self, nums: List[int]) -> int:
        pass

    def findNumberOfLIS1(self, nums: List[int]) -> int:
        numLen, maxSubIncLen, res = len(nums), 0, 0
        dp = [1] * numLen  # dp[i] 表示以 nums[i] 为结尾长度最长递增子序列的长度
        counts = [1] * numLen  # counts[i]表示以 nums[i] 为结尾的最长递增序列的个数, counts[i]，其等于所有满足 dp[j]+1=dp[i] 的 counts[j] 之和
        for i in range(numLen):
            for j in range(i - 1, -1, -1):
                if nums[j] < nums[i]:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        counts[i] = counts[j]
                    elif dp[j] + 1 == dp[i]:
                        counts[i] += counts[j]
            # 尝试更新最终结果
            if dp[i] > maxSubIncLen:
                maxSubIncLen = dp[i]
                res = counts[i]
            elif dp[i] == maxSubIncLen:
                res += counts[i]
        return res

    def findNumberOfLIS(self, nums: List[int]) -> int:
        return self.findNumberOfLIS1(nums)


if __name__ == "__main__":
    nums = [1, 3, 5, 4, 7]
    nums = [2, 2, 2, 2, 2]
    print(Solution().findNumberOfLIS(nums))
